/*
 ************************************************************************
 *                                                                      *
 *                     Binary Tree Routines Library                     *
 *                                                                      *
 * Author: Arash Partow - 2001                                          *
 * URL: http://www.partow.net                                           *
 *                                                                      *
 * Copyright notice:                                                    *
 * Free use of the Binary Tree Routines Library is permitted under the  *
 * guidelines and in accordance with the most current version of the    *
 * Common Public License.                                               *
 * http://www.opensource.org/licenses/cpl1.0.php                        *
 *                                                                      *
 ************************************************************************
*/


#ifndef INCLUDE_BINARY_TREE_HPP
#define INCLUDE_BINARY_TREE_HPP

#include <iostream>
#include <string>
#include <deque>


namespace binary_tree
{
   template <typename K, typename T>
   struct node
   {
      typedef node* node_ptr;
      T        value;
      K        key;
      int      n;
      node_ptr left;
      node_ptr right;
   };

   template <typename T, typename K, typename node_ptr>
   inline void init(node_ptr* node, const K& k, const T& v)
   {
      (*node) = new binary_tree::node<K,T>;
      (*node)->value  = v;
      (*node)->key    = k;
      (*node)->left   = 0;
      (*node)->right  = 0;
      (*node)->n      = 0;
   }

   template <typename node_ptr>
   inline void free(node_ptr node)
   {
      if (node == 0) return;
      if (node->left != 0) free(node->left);
      if (node->right!= 0) free(node->right);
      delete node;
   }

   template <typename T, typename K, typename node_ptr>
   inline node_ptr insert(node_ptr node, const K& k, const T& v)
   {
      if (node == 0)
      {
         node_ptr tmp = new binary_tree::node<T,K>;
         tmp->value = v;
         tmp->key   = k;
         tmp->left  = 0;
         tmp->right = 0;
         tmp->n     = 1;
         return tmp;
      }

      if (k < node->key)
         node->left  = insert(node->left,k,v);
      else
         node->right = insert(node->right,k,v);
      node->n++;
      return node;
   }

   template <typename node_ptr>
   inline node_ptr rotate_right(const node_ptr node)
   {
      if (node == 0) return node;
      node_ptr tmp = node->left;
      node->left = tmp->right;
      tmp->right = node;
      return tmp;
   }

   template <typename node_ptr>
   inline node_ptr rotate_left(const node_ptr node)
   {
      if (node == 0) return node;
      node_ptr tmp = node->right;
      node->right = tmp->left;
      tmp->left = node;
      return tmp;
   }

   template <typename node_ptr>
   inline node_ptr partition(node_ptr node, int k)
   {
      int t = ((node->left != 0) ? node->left->n : 0);
      if((t > k) && (node->left != 0))
      {
         node->left = partition(node->left,k);
         node = rotate_right(node);
      }
      else if ((t < k) && (node->right != 0))
      {
         node->right = partition(node->right,k - t - 1);
         node = rotate_left(node);
      }
      return node;
   }

   template <typename node_ptr>
   inline node_ptr balance(node_ptr node)
   {
      if ((node == 0) ||(node->n < 2)) return node;
      node = partition(node, node->n / 2);
      node->left  = balance(node->left);
      node->right = balance(node->right);
      return node;
   }

   template <typename node_ptr>
   inline node_ptr join(node_ptr a,node_ptr b)
   {
      if (b == 0) return a;
      b = partition(b,0);
      b->left = a;
      return b;
   }

   template <typename K, typename node_ptr>
   inline node_ptr delete_node(node_ptr node, const K& key)
   {
      if (node == 0) return 0;
      if (key < node->key) node->left = delete_node(node->left,key);
      if (key > node->key) node->right = delete_node(node->right,key);
      if (key == node->key)
      {
         node_ptr tmp = node;
         node = join(node->left,node->right);
         delete tmp;
      }
      return node;
   }

   template <typename K, typename node_ptr>
   inline bool exists(node_ptr node, const K& key)
   {
      if (node == 0) return false;
      if (node->key == key) return true;
      if (key < node->key)
         return exists(node->left,key);
      else
         return exists(node->right,key);
   }

   template <typename K, typename node_ptr>
   inline bool exists(node_ptr node, const K& key, unsigned int& hop_count)
   {
      if (node == 0) return false;
      if (node->key == key) return true;
      hop_count++;
      if (key < node->key)
         return exists(node->left,key,hop_count);
      else
         return exists(node->right,key,hop_count);
   }

   template <typename K, typename node_ptr>
   inline node_ptr find_node(node_ptr node, const K& key)
   {
      if (node == 0) return 0;
      if (node->key == key) return node;
      if (key < node->key)
         return find_node(node->left,key);
      else
         return find_node(node->right,key);
   }

   template <typename node_ptr>
   inline std::size_t max_depth(node_ptr node)
   {
      if (node == 0)
         return 0;
      else
         return 1 + std::max(max_depth(node->left),max_depth(node->right));
   }

   template <typename node_ptr>
   inline std::size_t min_depth(node_ptr node)
   {
      if (node == 0)
         return 0;
      else
         return 1 + std::min(min_depth(node->left),min_depth(node->right));
   }

   template <typename node_ptr>
   inline void recompute_depths(node_ptr node)
   {
      if (node == 0) return;
      std::deque<node_ptr> node_list;
      node_list.push_back(node);
      std::size_t nodes_on_level = 1;
      std::size_t child_nodes_for_level = 0;
      std::size_t current_level = 1;
      while (!node_list.empty())
      {
         for (std::size_t i = 0; i < nodes_on_level; ++i)
         {
            node_ptr current_node = node_list.front();
            node_list.pop_front();
            current_node->n = current_level;
            if (current_node->left)
            {
               node_list.push_back(current_node->left);
               ++child_nodes_for_level;
            }
            if (current_node->right)
            {
               node_list.push_back(current_node->right);
               ++child_nodes_for_level;
            }
         }
         if (nodes_on_level)
         {
            nodes_on_level = child_nodes_for_level;
            child_nodes_for_level = 0;
            current_level++;
         }
      }
   }

   template <typename node_ptr>
   inline void display(node_ptr node, char o, int level = 0)
   {
      if (node == 0) return;
      for (int i = 0; i < level; ++i) std::cout << " ";
      std::cout << o << " v:" << node->value << "\tn:" << node->n << std::endl;
      display(node->left, 'L',level + 1);
      display(node->right,'R',level + 1);
   }

   template <typename node_ptr>
   inline void preorder_display(node_ptr node, int level = 0)
   {
      if (node == 0) return;
      for (int i = 0; i < level; ++i) std::cout << " ";
      std::cout << " v:" << node->value << "\tn:" << node->n << std::endl;
      preorder_display(node->left, level + 1);
      preorder_display(node->right,level + 1);
   }

   template <typename node_ptr>
   inline void inorder_display(node_ptr node, int level = 0)
   {
      if (node == 0) return;
      inorder_display(node->left,level + 1);
      for (int i = 0; i < level; ++i) std::cout << " ";
      std::cout << " v:" << node->value << "\tn:" << node->n << std::endl;
      inorder_display(node->right,level + 1);
   }

   template <typename node_ptr>
   inline void postorder_display(node_ptr node, int level = 0)
   {
      if (node == 0) return;
      postorder_display(node->left, level + 1);
      postorder_display(node->right,level + 1);
      for (int i = 0; i < level; ++i) std::cout << " ";
      std::cout << " v:" << node->value << "\tn:" << node->n << std::endl;
   }

   template <typename node_ptr>
   inline void display(node_ptr node, std::string title = "")
   {
      std::cout << "|--" << title << "-----------|" << std::endl;
      display_tree(node,'h');
      std::cout << "|-------------|" << std::endl;
   }

   template <typename node_ptr>
   inline void topological_display(node_ptr node)
   {
      if (node == 0) return;
      std::deque<node_ptr> node_list;
      node_list.push_back(node);
      std::size_t nodes_on_level = 1;
      std::size_t child_nodes_for_level = 0;
      std::size_t current_level = 1;
      while (!node_list.empty())
      {
         std::cout << "Level[" << current_level << "]\t";
         for (std::size_t i = 0; i < nodes_on_level; ++i)
         {
            node_ptr current_node = node_list.front();
            node_list.pop_front();
            if (current_node->left)
            {
               node_list.push_back(current_node->left);
               ++child_nodes_for_level;
            }
            if (current_node->right)
            {
               node_list.push_back(current_node->right);
               ++child_nodes_for_level;
            }
            std::cout << current_node->value << " ";
         }
         if (nodes_on_level)
         {
            nodes_on_level = child_nodes_for_level;
            child_nodes_for_level = 0;
            current_level++;
            std::cout << std::endl;
         }
      }
   }
}// namespace binary_tree


#endif
